/**
 * \file    state.cpp
 * \brief   Parser generator.
 * \author  Jérôme LAURENS
 * \version 0.1
 * \date    September 23, 2014
 *
 * Reads a LALR(1) grammar, generates a parser based on a template file.
 * This is based on lemon parser generator, but has strongly been
 * revisited.
 *
 */

#include "generator.h"
#include "state.h"
#include "item.h"
#include "rule.h"
#include "symbol.h"
#include "action.h"

LPP_NAMESPACE_BEGIN

int compare(State const & __a, State const & __b) {
    if (&__a==&__b) return 0;
    if (__a.state_id_m==0) {
        return -1;
    } else if (__b.state_id_m==0) {
        return 1;
    }
    auto i = __a.core_items().cbegin();
    auto const & e = __a.core_items().cend();
    auto j = __b.core_items().cbegin();
    auto const & f = __b.core_items().cend();
    while (true) {
        int rc = compare(**i,**j);
        if (rc) return rc;
        if (++i!=e) {
            if (++j!=f) {
                continue;
            }
            return 1;
        } else if (++j!=f) {
            return -1;
        } else {
            return 0;
        }
    }
}
bool operator==(const StateRef & a, const StateRef & b) {
    return !(a->hash()!=b->hash()||compare(*a, *b)!=0);
}
int compare(StateRef const & __a, StateRef const & __b) {
    return compare_Ref<StateRef>(__a,__b);
}
int compare(StateWrap const & __a, StateWrap const & __b) {
    return compare_Wrap<StateWrap>(__a,__b);
}
bool operator==(const StateWrap & a, const StateWrap & b) {
    return compare(a, b)==0;
}

bool State::add_core_item(ItemRef const & I) {
    if (core_items_m.insert(I).second) {
        hash_combine<ItemRef>(hash_m,I);
        ordered_items_m.push_back(I);
        ordered_core_items_m.push_back(I);
        return true;
    }
    return false;
}

// see https://code.google.com/p/fast-hash/
// unused, yet ?
#define mix(h) ({                                       \
                        (h) ^= (h) >> 23;               \
                        (h) *= 0x2127599bf4325c37ULL;   \
                        (h) ^= (h) >> 47; })
#define LPP_EMPLACE emplace_front
#define LPP_GET_EMPLACED front
ActionRef const & State::add_shift_action(SymbolRef const & symbol, StateRef const & state) {
    actions_m.LPP_EMPLACE(std::make_shared<Action>(symbol,state));
    return did_add_action();
}

ActionRef const & State::add_reduce_action(SymbolRef const & symbol, RuleRef const & rule) {
    ActionRef const & A = action(symbol);
    if (A) {
        auto const i = std::find(actions_m.begin(),actions_m.end(),A);
        conflict_actions_m.push_back(A);
        actions_m.erase(i);
    }
    actions_m.LPP_EMPLACE(std::make_shared<Action>(symbol,rule));
    return did_add_action();
}

ActionRef const & State::add_action(Action::Type const type, SymbolRef const & symbol) {
    ActionRef const & A = action(symbol);
    if (A) {
        auto const i = std::find(actions_m.begin(),actions_m.end(),A);
        conflict_actions_m.push_back(A);
        actions_m.erase(i);
    }
    actions_m.LPP_EMPLACE(std::make_shared<Action>(type,symbol));
    return did_add_action();
}

ActionRef const & State::did_add_action() {
    ActionRef const & out = actions_m.LPP_GET_EMPLACED();
    SymbolRef const & lookahead = out->lookahead();
    if (lookahead->is_terminal()) {
        terminal_actions_m.erase(lookahead);
        terminal_actions_m.emplace(lookahead,out);
    } else if (lookahead->is_non_terminal()) {
        non_terminal_actions_m.erase(lookahead);
        non_terminal_actions_m.emplace(lookahead,out);
    } else {
        DEBUG_MESSAGE("WHAT KIND OF ACTION?");
    }
    return out;
}

/* Reduce the size of the action tables, if possible, by making use
** of defaults.
**
** In this version, we take the most frequent reduce action and make
** it the default.  Except, there is no default if the wildcard token
** is a possible look-ahead.
*/
void State::compress_tables() {
    auto i = actions_m.cbegin();
    auto e = actions_m.cend();
    bool uses_wildcard = false;
    RuleRef best_R;
    SymbolIndex best_n = 0;
    for (;i!=e;++i) {
        if ((*i)->is_shift() && generator_m.grammar()->is_wildcard((*i)->lookahead())) {
            uses_wildcard = true;
            break;
        }
        if ((*i)->is_reduce()) {
            RuleRef const & R = (*i)->reduce_rule();
            if (R->lhs_is_start() || R==best_R) continue;
            SymbolIndex n = 1;
            ActionRefList::const_iterator ii=i;
            for (; ii!=e; ++ii) {
                if ((*ii)->is_reduce()) {
                    RuleRef const & RR = (*ii)->reduce_rule();
                    if (RR==best_R) continue;
                    if (RR==R) ++n;
                }
            }
            if (n>best_n) {
                best_n = n;
                best_R = R;
            }
        }
    }
    if (uses_wildcard || best_n<1) return; // no compression
    /* Combine matching reduce actions into a single default */
    bool first = true;
    for (ActionRef & a: actions_m) {
        if (a->is_reduce() && a->reduce_rule() == best_R) {
            if (first) {
                first = false;
                if (a->is_terminal()) {
                    terminal_actions_m.erase(a->lookahead());
                }
                a->set_default();
                DEBUG_MESSAGE("DEFAULT ACTION: %s",Description()(a).c_str());
            } else {
                a->set_not_used();// the first one does the job
                DEBUG_MESSAGE("UNUSED ACTION: %s",Description()(a).c_str());
            }
        }
    }
    sort_actions();

#if 0
    static int actioncmp(
            struct action *ap1,
            struct action *ap2
            ){
        int rc;
        rc = ap1->sp->index - ap2->sp->index;
        if( rc==0 ){
            rc = (int)ap1->type - (int)ap2->type;
        }
        if( rc==0 && ap1->type==REDUCE ){
            rc = ap1->x.rp->index - ap2->x.rp->index;
        }
        if( rc==0 ){
            rc = (int) (ap2 - ap1);
        }
        return rc;
    }
#endif
}

#ifndef LPP_NO_DEFAULT_ACTIONS

void State::setup_default_actions() {
    typedef std::pair<Action::Type,Index> Pair;
    typedef std::vector<ActionRef> Actions;
    typedef std::map<Pair,Actions> Map;
    if (terminal_actions_count()) {
        Map m;
        Pair p;
        Index max = 0;
        for (ActionRefMap::value_type const & V: terminal_actions()) {
            ActionRef const & A = V.second;
            if (A->can_default()) {
                Pair p(A->type(),A->pre_code());
                m[p].push_back(A);
            }
        }
        for (Map::value_type const & V: m) {
            if (V.second.size()>max) {
                p = V.first;
            }
        }
        default_terminal_action(m[p].front());
        for (ActionRef & A: m[p]) {
            A->use_default(true);
        }
    }
    if (non_terminal_actions_count()) {
        Map m;
        Pair p;
        Index max = 0;
        for (ActionRefMap::value_type const & V: non_terminal_actions()) {
            ActionRef const & A = V.second;
            if (A->can_default()) {
                Pair p(A->type(),A->pre_code());
                m[p].push_back(A);
            }
        }
        for (Map::value_type const & V: m) {
            if (V.second.size()>max) {
                p = V.first;
            }
        }
        default_non_terminal_action(m[p].front());
        for (ActionRef & A: m[p]) {
            A->use_default(true);
        }
    }
}

#endif

LPP_NAMESPACE_END
